package com.teng.algorithm.sort;

import java.util.Arrays;

/**
 * @author liangtl
 * @Date 2023/2/26
 * @Return
 * @Description:
 */
public class InsertSortTime {
    public static void main(String[] args) {
        int[] arr = new int[100000];
        for (int i = 0; i < 100000; i++) {
            arr[i] = (int) (Math.random() * 800000);
        }
        long start = System.currentTimeMillis();
        System.out.println("排序开始,请等待.......");
        int[] insertSort = insertSort(arr);
        System.out.println("排序完成！");
        long end = System.currentTimeMillis();
        System.out.println("100000个数据插入排序时间为： " + (end - start) + "ms");
        //System.out.println(Arrays.toString(arr));
    }

    public static int[] insertSort(int[] arr) {
        int value = 0;
        int index = 0;
        for (int i = 1; i < arr.length; i++) {
            value = arr[i];
            index = i - 1;
            while (index >= 0 && arr[index] > value) {
                arr[index + 1] = arr[index];
                index--;
            }
            if ( arr[index + 1] != i) {
                arr[index + 1] = value;
            }
        }
        return arr;
    }
}
